"""
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1   输入：n = 4, k = 2
        输出：
        [
          [2,4],
          [3,4],
          [2,3],
          [1,2],
          [1,3],
          [1,4],
        ]
"""


def backtracking(tem, n, k, hight):
    if len(tem) == k:
        ans.append(tem.copy())
        return
    for i in range(hight, n + 1):
        tem.append(i)
        backtracking(tem, n, k, i + 1)
        tem.pop(-1)
    return


tem = []
ans = []
n = 4
k = 3
backtracking(tem, n, k, 0)
print(ans)
